#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
/**
 * @方法: 哈希表的映射用法
 * @时间复杂度: o()
 * @空间复杂度: o()
 * @评价:
*/ 
class Solution {
    private: 
        int sz;
        unordered_map<int, int> mp;
public:
    Solution(int n, vector<int>& blacklist) {
        sz = n - blacklist.size();
        for(int b : blacklist) mp[b] = -1;
        int last = n - 1;
        for(int b : blacklist){
            if(b >= sz) continue;
            while(mp.count(last)) last--;
            mp[b] = last;
            last--;
        }
    }
    
    int pick() {
        int r = rand()%sz;
        if(mp.count(r)) return mp[r];
        return r;
    }
};